package data_structs;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

import util.SequenceComparator;

import errors.DuplicateKey;

public class HashRB<E> {

	/**
	 * 
	 * @author DC
	 *
	 * @param <E>
	 * Only used during resizing of the hash table
	 */
	private class HashIterator<E> implements Iterator<E> {
//		private E[] nodes;
//		private int hashIndex, treeIndex, treeSize;
		private int index;
		private int objsLeft;
		
		public HashIterator() {
			/*//1st Iterator Version
			nodes = (E[]) new Object[numObjects];
			index = 0;
			//Iterate through hashArr and copy elements to nodes[]
			for( int i = 0, j = 0; i < tableSize; i++ ) {
				TreeMap tree = hashArr[i];
				Set<E> set = tree.keySet();
				for( E data : set )
					nodes[j++] = data;
			}
			*/
			
			/*//2nd Iterator Version
			hashIndex = treeIndex = 0;
			treeSize = hashArr[0].size();
			Set<E> set = (Set<E>) hashArr[0].keySet();
			nodes = (E[]) new Object[treeSize];
			int j = 0;
			for( E data : set )
				nodes[j++] = data;
			*/
			
			//3rd Iterator Version
			index = 0;
			objsLeft = numObjects;
		}
		
		public boolean hasNext() {
			/*//1st Iterator Version
			 return index < numObjects;
			 */
			
			/*//2nd Iterator Version
			//Check if end of tree has been reached
			if( treeIndex >= treeSize ) {
				//Clear the tree since it is finished
				hashArr[hashIndex].clear();
				//Loop until a tree containing objects is reached
				do {
					//Make sure end of main hash array isn't reached
					if( ++hashIndex >= tableSize )
						return false;
					treeSize = hashArr[hashIndex].size();
				} while( treeSize == 0 );
				//Filled tree found
				//Fill nodes array with objects
				treeIndex = 0;
				Set<E> set = (Set<E>) hashArr[hashIndex].keySet();
				nodes = (E[]) new Object[treeSize];
				int j = 0;
				for( E data : set )
					nodes[j++] = data;
			}
			//Still objects in the current tree
			return true;
			*/
			
			//3rd Iterator Version
			return objsLeft != 0;
		}
		
		public E next() {
			/*//1st Iterator Version
			return nodes[index++];
			*/
			
			/*//2nd Iterator Version
			return nodes[treeIndex++];
			*/
			
			//3rd Iterator Version
			while( hashArr[index].size() == 0 )
				hashArr[index++] = null;
			E ret = (E) hashArr[index].lastKey();
			hashArr[index].remove(ret);
			objsLeft--;
			return ret;
		}
		
		public void remove() {
			throw new UnsupportedOperationException("Remove not allowed.");
		}
	}
	
	//Global variables
	private TreeMap<E,E>[] hashArr;
	private int tableSize;
	private int numObjects;
	private int numOfResize = 0;
	private static double maxLoadFactor = 0.75;
	
	public HashRB() {
		this(9973);
	}
	
	public HashRB(int tableSize) {
		
		if( tableSize <= 0) {
			this.tableSize = 9973;
			System.err.println("Table size must be a positive integer. Setting to 9973.");
		}
		else
			this.tableSize = tableSize;
		numObjects = 0;
		hashArr = new TreeMap[tableSize];
		for( int i = 0; i < tableSize; i++ )
			hashArr[i] = new TreeMap(new SequenceComparator());
	}
	
	public boolean add(E obj) throws DuplicateKey {
//		if( isFull() )
//			resize();
		
		int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
		TreeMap<E,E> tree = hashArr[index];
		//Check if object already exists
		if( !tree.containsKey(obj) ) {
			if( tree.put(obj, obj) == null ) {
				numObjects++;
				return true;
			}
			//Fail if tree attempted to add but returned an object
			else
				throw new DuplicateKey("Attempted and failed to add "+obj+".\n" +
				"Tree already contains key.");
		}
		//Tree already has the object
		//Change tree's comparator to implement a force-add
		//Change object's compare method to implement a force-add
		return false;
	}

	//Return the list of found objects' toString
	public ArrayList<E> contains(E obj) {
		if( isEmpty() )
			return null;
		int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
		TreeMap<E,E> tree = hashArr[index];
		
		Set<E> set = tree.keySet();
		Iterator<E> iter = set.iterator();
		ArrayList<E> res = new ArrayList<E>();
		while( iter.hasNext() ) {
			E current = (E) iter.next();
			if( ((Comparable<E>)current).compareTo(obj) == 0 )
				res.add(current);
		}
		return res;
	}

	public E remove(E obj) {
		throw new UnsupportedOperationException("Remove not allowed.");
	}

	public TreeMap<E,E>[] allElements() {
		return hashArr;
	}

	public double loadFactor() {
		return (double) numObjects/tableSize;
	}

//	public void resize() {
//		//Resize info
//		numOfResize++;
//		System.out.println("Resize #"+numOfResize+"\nTableSize before resize: "+tableSize+"\n" +
//				"LoadFactor: "+loadFactor()+"\nNumber of elements: "+numObjects+"\n");
//		System.out.println("Memory left over: "+java.lang.Runtime.getRuntime().freeMemory());
//		
//		//Copy elements with iterator
//		HashIterator<E> iter = new HashIterator();
//		
//		//Double the table size then increment to a semi-prime number
//		//If can be divided by any first six prime numbers
//		//evenly, increment by 1
//		tableSize <<= 1;
//		while( tableSize % 2 == 0 || tableSize % 3 == 0 || tableSize % 5 == 0
//			|| tableSize % 7 == 0 || tableSize % 9 == 0 || tableSize % 11 == 0 )
//				tableSize++;
//		
//		//Make new hashArr with new table size
//		hashArr = new TreeMap[tableSize];
//		for( int i=0; i < tableSize; i++ )
//			hashArr[i] = new TreeMap(new SequenceComparator());
//		
//		//Rehash all elements and add to hashArr
//		while( iter.hasNext() ) {
//			E obj = iter.next();
//			int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
//			TreeMap<E,E> tree = hashArr[index];
//			tree.put(obj, obj);
//		}
//		System.out.println("Load Factor after resize: "+loadFactor()+"\n");
//	}
	
	public void resize() {
		//Resize info
		numOfResize++;
		System.out.println("Resize #"+numOfResize+"\nTableSize before resize: "+tableSize+"\n" +
				"LoadFactor: "+loadFactor()+"\nNumber of elements: "+numObjects+"\n");
		System.out.println("Memory left over: "+java.lang.Runtime.getRuntime().freeMemory());
		
		//Copy elements with iterator
		HashIterator<E> iter = new HashIterator();
		
		
		//Double the table size then increment to a semi-prime number
		//If can be divided by any first six prime numbers
		//evenly, increment by 1
		tableSize <<= 1;
		while( tableSize % 2 == 0 || tableSize % 3 == 0 || tableSize % 5 == 0
				|| tableSize % 7 == 0 || tableSize % 9 == 0 || tableSize % 11 == 0 )
					tableSize++;
		
		TreeMap<E,E>[] tmp = new TreeMap[tableSize];
		for( int i = 0; i < tableSize; i++ )
			tmp[i] = new TreeMap(new SequenceComparator());
		
		while( iter.hasNext() ) {
			E obj = iter.next();
			int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
			TreeMap<E,E> tree = tmp[index];
			tree.put(obj, obj);
		}
		
		hashArr = tmp;
		System.out.println("Load Factor after resize: "+loadFactor()+"\n");
	}

	public int numObjects() {
		return numObjects;
	}

	public boolean isEmpty() {
		return numObjects == 0;
	}

	public boolean isFull() {
		return loadFactor() >= maxLoadFactor;
	}
	
	private void delete(E obj) {
		
	}
	
	//Print out info about hash table
	public String hashStatus() {
		int zero, least5, least10, least100, more100;
		zero = least5 = least10 = least100 = more100 = 0;
		for( int i = 0; i < tableSize; i++ ) {
			int num = hashArr[i].size();
			if( num == 0 ) zero++;
			else if( num <= 5 ) least5++;
			else if( num <= 10 ) least10++;
			else if( num <= 100 ) least100++;
			else more100++;
		}
		double pctNotUsed = (double) zero/tableSize*100;
		return "***HASH STATUS***\n$" +
				"Trees with no items: "+zero+"\n$" +
				"Trees with 1 to 5 items: "+least5+"\n$" +
				"Trees with 6 to 10 items: "+least10+"\n$" +
				"Trees with 11 to 100 items: "+least100+"\n$" +
				"Trees with more than 100 items: "+more100+"\n$" +
				"Table Size: "+tableSize+"\n$" +
				"Percentage not in use: "+pctNotUsed+"%\n$" +
				"Current Load Factor: "+loadFactor()+"\n$" +
				"Number of resizes: "+numOfResize+"\n";
	}
}
